#define _CRT_SECURE_NO_WARNINGS
#include "stack_queue.h"
#include <stack>
#include <string>
class Solution {
public:
    vector<string> ret;
    string path;
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }
    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(path);
            return;
        }
        int i;
        for (i = pos; i < s.size(); i++)
        {
            if (islower(s[i]))
            {
                path += toupper(s[i]);
                dfs(s, i + 1);
                path.erase(i);
            }
            if (isupper(s[i]))
            {
                path += tolower(s[i]);
                dfs(s, i + 1);
                path.erase(i);
            }
            path += s[i];
        }
        if (i == s.size())
        {
            ret.push_back(path);
        }
    }
};

int main()
{
    string s("a1b2");
    letterCasePermutation(s);
    return 0;
}
//bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//    // write code here
//    stack<int> st1;
//    int size = pushV.size();
//    int j = 0;
//    for (int i = 0; i < size; i++)
//    {
//        st1.push(pushV[i]);
//        while (!st1.empty() && st1.top() == popV[j])
//        {
//            st1.pop();
//            j++;
//        }
//    }
//
//    while (!st1.empty())
//    {
//        if (st1.top() != popV[j])
//        {
//            return false;
//        }
//        st1.pop();
//        j++;
//    }
//    return true;
//
//}
//int main()
//{
//    vector<int> nums1 = { 2,1,0 };
//    vector<int> nums2 = { 1,2,0 };
//    IsPopOrder(nums1, nums2);
//    return 0;
//}
//int main()
//{
//	vector<int> v = { 1,2,3,4,5,6,7 };
//	bit::stack<int> st(v.begin(), v.end());
//	bit::queue<int> q(v.begin(), v.end());
//	while (!st.empty())
//	{
//		cout << st.top() << " ";
//		st.pop();
//	}
//	cout << endl;
//	while (!q.empty())
//	{
//		cout << q.top() << " ";
//		q.pop();
//	}
//
//	return 0;
//}



//class MinStack {
//public:
//    MinStack()
//        :st()
//        , st1()
//    {
//
//    }
//
//    void push(int val) {
//        st.push(val);
//        if (st1.empty())
//        {
//            st1.push(val);
//        }
//        else
//        {
//            if (val <= st1.top())
//                st1.push(val);
//        }
//    }
//
//    void pop() {
//        if (st.top() == st1.top())
//            st1.pop();
//        st.pop();
//    }
//
//    int top() {
//        return st.top();
//    }
//
//    int getMin() {
//        return st1.top();
//    }
//    stack<int> st;
//    stack<int> st1;
//};


//class Solution {
//public:
//    vector<string> ret;
//    string path;
//    vector<string> generateParenthesis(int n) {
//        if (n == 0)
//            return ret;
//        dfs(0, 0, n);
//        return ret;
//    }
//    void dfs(int left, int right, int n)
//    {
//        if (left == n && right == n)
//        {
//            ret.push_back(path);
//        }
//        if (left < n)
//        {
//            path += '(';
//            dfs(left + 1, right, n);
//            path.pop_back();
//        }
//        if (right < left)
//        {
//            path += ')';
//            dfs(left, right + 1, n);
//            path.pop_back();
//        }
//    }
//};
//
//
//
//class Solution {
//public:
//    vector<vector<int>> ret;
//    vector<int> path;
//    vector<vector<int>> combine(int n, int k) {
//        if (k == 0)
//            return ret;
//        dfs(1, n, k);
//        return ret;
//    }
//    void dfs(int pos, int n, int k)
//    {
//        if (k == 0)
//        {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = pos; i <= n - k + 1; i++)
//        {
//            path.push_back(i);
//            dfs(i + 1, n, k - 1);
//            path.pop_back();
//        }
//    }
//};
//
//class Solution {
//public:
//    int path = 0;
//    int ret = 0;
//    int findTargetSumWays(vector<int>& nums, int target) {
//        dfs(nums, 0, target);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos, int target)
//    {
//        if (nums.size() == pos)
//        {
//            if (path == target)
//                ret++;
//            return;
//        }
//        path += nums[pos];
//        dfs(nums, pos + 1, target);
//        path -= nums[pos];
//
//        path -= nums[pos];
//        dfs(nums, pos + 1, target);
//        path += nums[pos];
//
//    }
//};
//
//
//class Solution {
//public:
//    int aim;
//    vector<int> path;
//    vector<vector<int>> ret;
//    int sum = 0;
//    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//        aim = target;
//        dfs(candidates, 0);
//        return ret;
//    }
//    void dfs(vector<int>& candidates, int pos)
//    {
//        if (sum >= aim)
//        {
//            if (sum == aim)
//                ret.push_back(path);
//            return;
//        }
//        for (int i = pos; i < candidates.size(); i++)
//        {
//            path.push_back(candidates[i]);
//            sum += candidates[i];
//            dfs(candidates, i);
//            sum -= candidates[i];
//            path.pop_back();
//        }
//    }
//};